Random Cuts are Optimal for Explainable k-Medians